The invention relates to rendering polygons in three-dimensional graphics systems.
As shown in FIGS. 1 and 2, for purposes of displaying a three-dimensional (3-D) image 6 on a two-dimensional (2-D) display 21, a typical graphics system 17 forms an image representative of the projection of the 3-D image 6 onto a planar viewing window 11. Thus, 3-D objects 8 of the image 6 are transformed into planar, 2-D objects 9 for viewing on the display 21.
The physical properties (e.g., size and appearance) of each object 9 are typically defined by a data structure 12 stored in a memory 15 of the graphics system 17. A graphics engine 14 of the system 17 typically renders the objects 9 by performing affine transformations (e.g., rotation and translation) of the objects 9 and forming image data which is stored in a buffer 18. A video output circuit 22 uses the image data stored in the buffer 18 to form horizontal scan lines (and thus, the objects 9) on the display 21.
Referring to FIG. 3, the graphics engine 14 uses the buffer 18 to build each frame 22 (i.e., one screen of the image) of the image by subdividing the frame 22 into horizontal bands 24. As shown in FIG. 4, to facilitate processing of the objects 9 by the graphics engine 14, the 2-D objects 9 (e.g., the object 9b) are typically represented by an arrangement of polygons (e.g., triangles 30) with the vertexes of the polygons stored in the data structures 12. The triangle 30 may represent a planar surface, or facet, of the object 9, and each triangle 30 has a set of characteristics (e.g., a lighting, a base color, and a texture) which determine a color fill pattern for the triangle. Facets (e.g., the front facet of the object 9b) of the object 9 may be defined by more than one triangle 30. To form the image data, the graphics engine 14 typically builds each triangle 30, one at a time, inside the buffer 18. The shape of the triangles 30 may be altered by objects 9 that penetrate or partially hide the triangle 30.
Referring to FIG. 5, the triangles 30 frequently do not fit entirely within the boundaries of the horizontal bands 24. As a result, portions of the triangle 30 may be clipped by the horizontal band 24. For example, one horizontal band 24a may have polygons 36 formed from portions of three triangles 30. Each polygon 36 is not only defined by edges 31 of the original triangle 30 but also by edges 34 of the horizontal band 24a.
The edges of the polygon 36 only define the boundaries of the polygon 36. To fill in, or paint, the interior of the polygon 36, the graphics engine 14 subdivides the horizontal band 24 into rectangular scan windows, or tiles 39 (for clarity, only one tile is shown in FIG. 5). The polygon 36 may span across more than one tile 39.
The graphics engine 14 typically fills in the interior of the polygons 36, one at a time, with the color pattern associated with the triangle 30 (associated with the polygon 36). Thus, for each pixel inside the polygon 36, the graphics engine 14 transfers an associated color value (e.g., a sixteen bit value that represents the color of the pixel) to the buffer 18.
Because the graphics engine 14 cannot see the edges of the polygon 36, the graphics engine 14 searches, or scans, pixels inside the tile 39 to locate pixels inside the polygon 36. The graphics engine 14 follows a pattern 37 governed by a major scan axis 42 and a minor scan axis 40, beginning at a starting point 43 at one of the corners of the tile 39. Along the pattern 37, the graphics engine 14 tests each pixel to determine if the pixel is inside the polygon 36, and if so, the graphics engine 14 transfers the associated color value to the buffer 18. If, however, the pixel is outside of the polygon 36, then no color value is transferred to the buffer 18.
In the scan, the graphics engine 14 typically advances one pixel along the major scan axis 42 after a line of pixels are scanned along the minor scan axis 40. For example the scan might begin at the corner 43 of the tile 39, with the major scan axis 42 having a vertical orientation and the minor scan axis 40 having a horizontal orientation. In this example, the graphics engine 14 begins each minor scan at the left vertical edge of the tile 39, i.e., the major scan path is along the left vertical edge of the tile 39. After each horizontal line of pixels is scanned from left to right (i.e., away from the corner 43 and along the minor scan axis 40), the graphics engine 14 advances vertically one pixel (i.e., away from the corner 43 and along the major scan axis 42) before scanning another horizontal line of pixels.
As shown, in this example, the major scan path eventually goes outside of the polygon 36 before all pixels inside of the polygon 36 are scanned. Thus, after the scan advances past a point 41 along the major scan path, the graphics engine 14 begins each minor scan outside of the polygon 36 and time is consumed testing pixels outside of the polygon 36, i.e., pixels to the left of the edge 31a.
Before scanning the tile 39, the graphics engine 14 typically selects the directions for the major 42 and minor 40 scan axes, along with the location of the starting point 43. In a graphics architecture known as the Talisman architecture, the starting point 43 (one of the corners of the tile 39) is chosen based on the angular orientations of the edges of the polygon that cross the tile 39. Once the starting point 43 is determined, the two scanning directions are defined; however, which direction is the major scan direction and which direction is the minor scan direction is left to be determined. If one of the edges of the tile 39 are known to contain pixels inside of the polygon 36 (based on the angular orientations of the edges), then the graphics engine 14 orients the major scan axis to follow that edge. Otherwise, the Talisman architecture directs that the width and height of the tile 39 govern the selection of the directions of the major 42 and minor 40 scan axes. As shown in FIG. 5, these criteria do not ensure that the scan pattern remains substantially inside of the polygon 36.